2 results listed
Düğüm örtüsü problemi çizge teorisi alanında sıklıkla çalışılan çok önemli bir problemdir. Ağ bağlantılarının izlenmesi için güvenli noktaların oluşturulması, yolların izlenmesi için kameraların yerleştirilmesi ve filogenetik ağaçların oluşturulması gibi çok önemli uygulama alanları vardır. Düğüm örtüsü problemi NP-ZOR sınıfı içerisinde yer aldığı için bilinen algoritmalar ile polinom zamanda en iyi çözümü bulmak mümkün değildir. Bu sebepten dolayı düğüm örtüsü problemini polinom zamanda çözmek için sezgisel algoritmalar veya yakınsama algoritmaları kullanılmaktadır. Bu çalışmada açgözlü algoritma, 2-yakınsama algoritması ve öz indirgeme yaklaşımını kullanan ve en iyi sonucu veren iki algoritma (VC1 ve VC2) olmak üzere toplam dört algoritmanın teorik ve pratik karşılaştırılması yapılmıştır. Alınan benzetim sonuçlarına göre açgözlü sezgisel algoritma kısa zamanda en iyi sonucu veren algoritmalara yakın sonuçlar vermiştir. Çalışma zamanı açısından, en iyi sonucu veren algoritmalar açgözlü ve 2-yakınsama algoritmasından daha kötü sonuçlar vermiştir. Bunun yanı sıra VC2 algoritmasının VC1 algoritmasına göre 1000 kat daha hızlı çalıştığı gözlemlenmiştir.
Akademik Bilişim
AB
Yasin Yiğit
Orhan Dağdeviren
Telsiz Duyarga ve Aktör Ağlarında (TDAA’nda) bazı düğümlerin bozulması ağın bağlantısını koparır ve diğer aktif düğümlerin iletişimlerini engeller. k-bağlı ağlarda herhangi k-1 düğümün bozulması ağın bağlantısını zedelemez. k-bağlılık denetleme algoritmaları, mevcut topolojinin k değerini hesaplamak için kullanılmaktalardır. Bir ağın k değeri o ağın asgari düğüm derecesi, her iki düğümün arasında asgari bağımsız patikaların sayısı, kritik düğümlerin olup olmadığı ve ağın yoğunluğuyla ilgili önemli bilgiler verebilir. Bu çalışmada k-bağlılık denetleme problemi için tasarlanan merkezi ve dağıtık algoritmaları inceledikten sonra, bir merkezi algoritması ve en son önerilen PACK ve DECK isimli dağıtık algoritmaların performansı değerlendirilmiştir. Merkezi algoritmada ağın topoloji bilgileri bir düğümde toplanır ve k değeri elde edilen çizge üzerinden bulunur. PACK algoritması düğümlerin arasındaki bağımsız patikaları boyayarak k’yı yüksek oranda doğru bulmaktadır. Bazı topolojilerde PACK algoritmasının bulduğu değer ağın gerçek k değerinden düşük olabilir. DECK algoritmasında ağın k değeri 3 aşama sonrasında her zaman doğru bulunmaktadır. Bu çalışmada PACK, DECK ve Central algoritmalarının performansı, simülasyon ortamında ve gerçek ağlar üzerinde karşılaştırılmıştır.
Akademik Bilişim
AB
Vahid Khalilpour Akram
Yasin Yiğit
Orhan Dağdeviren